package com.company.algo.DP.base;

/**1504. 统计全 1 子矩形
 * 给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。
 * 方法1：动态规划(枚举)
 * 定义:dp[i][j]表示以(i,j)为左下角的子矩阵个数，容易得出递推式：
 * 转移：dp[i][j] =
 *      1. dp[i][j] = 0, if mat[i][j] == 0
 *      2. dp[i][j] = dp[i][j-1]+1, if mat[i][j] == 1
 * 有了dp数组后，如果要统计以(i,j)为右下角满足条件的子矩阵，就可以直接枚举子矩阵的高，即遍历k=i~0,当k满足条件，k--，
 * 最终以(i,j)为右下角满足条件的矩阵个数为res = res + col
 */
public class count_submatrices_with_all_ones {
    public int numSubmat(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[][] row = new int[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (j == 0) {
                    row[i][j] = mat[i][j];
                } else if (mat[i][j] != 0) {
                    row[i][j] = row[i][j - 1] + 1;
                } else {
                    row[i][j] = 0;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int col = row[i][j];
                for (int k = i; k >= 0 && col != 0; --k) {
                    col = Math.min(col, row[k][j]);
                    ans += col;
                }
            }
        }
        return ans;
    }

}
